package zwp.exercise.intereview.base.sort.QuickSort;

import java.util.Arrays;

/**
 * @Author zwp14
 * @create 2024/6/29 11:13
 * @description 快速排序-单边循环复习
 */
public class QuickSort1Review {
    public static void main(String[] args) {
        //定义数组
        int[] array = {5, 3, 7, 2, 9, 8, 1, 4};

        int r = array.length -1;
        int l = 0;

        //单边排序方法


        recursion(array,l,r);
    }

    //递归
    private static void recursion(int[] array, int l, int r) {
        if (l>=r){
            return;
        }
        int sort = sort(array,l,r);
        recursion(array,l,sort-1);
        recursion(array,sort+1,r);
    }

    //单边排序
    private static int sort(int[] array, int l, int r) {

        //标记sign,
        int sign = r;
        //分界点元素值
        int value = array[l];

        for (int i = r; i > l; i--) {
            if (value < array[i]){
                exchange(array, sign, i);
                sign--;
            }
        }
        exchange(array,l,sign);
        System.out.println(Arrays.toString(array));
        return sign;
    }

    private static void exchange(int[] array, int sign, int i) {
        int temp = array[i];
        array[i] = array[sign];
        array[sign] = temp;
    }
}
